package leetcode.D200.T102;

import util.TreeNode;

import java.util.*;

class Solution {
    /**
     * 解法1：通过新的数据结构来记录层信息
     * @param root
     * @return
     */
    /*class Node {
        int level;
        TreeNode node;
        Node(TreeNode n, int l) { node = n; level = l; }
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        Deque<Node> dq = new LinkedList<>();
        dq.addLast(new Node(root, 0));
        while(!dq.isEmpty()) {
            Node front = dq.removeFirst();
            if(front.node != null) {
                if(front.level >= result.size()) {
                    List<Integer> list = new LinkedList<>();
                    list.add(front.node.val);
                    result.add(list);
                } else {
                    List<Integer> list = result.get(front.level);
                    list.add(front.node.val);
                }
                dq.addLast(new Node(front.node.left, front.level + 1));
                dq.addLast(new Node(front.node.right, front.level + 1));
            }
        }
        return result;
    }*/

    /**
     * 解法2：通过另一个队列来记录层信息
     * @param root
     * @return
     */
    /*public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        if(root == null) {
            return results;
        }
        Deque<TreeNode> dqNode = new LinkedList<>();
        Deque<Integer> dqLevel = new LinkedList<>();
        List<Integer> temp = new ArrayList<>();
        dqNode.addLast(root);
        dqLevel.addLast(1);
        int lastLevel = 1;
        while (!dqNode.isEmpty()) {
            TreeNode front = dqNode.removeFirst();
            int level = dqLevel.removeFirst();
            if(level > lastLevel) {
                results.add(new ArrayList<>(temp));
                temp.clear();
            }
            temp.add(front.val);
            lastLevel = level;
            if(front.left != null) {
                dqNode.addLast(front.left);
                dqLevel.addLast(level + 1);
            }
            if(front.right != null) {
                dqNode.addLast(front.right);
                dqLevel.addLast(level + 1);
            }
        }
        results.add(new ArrayList<>(temp));
        return results;
    }*/

    /**
     * 解法3：逐层循环，而不是逐个节点循环，这样每次循环通过获取队列的大小，就能得知该层节点的个数
     * @param root
     * @return
     */
    /*public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        if(root == null) {
            return results;
        }
        Deque<TreeNode> dq = new LinkedList<>();
        dq.addLast(root);
        while (!dq.isEmpty()) {
            int size = dq.size();
            List<Integer> temp = new ArrayList<>();
            for(int i=0; i<size; ++i) {
                TreeNode front = dq.removeFirst();
                temp.add(front.val);
                if(front.left != null) {
                    dq.addLast(front.left);
                }
                if(front.right != null) {
                    dq.addLast(front.right);
                }
            }
            results.add(temp);
        }
        return results;
    }*/

    // 二刷
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;
        List<Integer> temp = new ArrayList<>();
        Deque<TreeNode> dq = new LinkedList<>();
        dq.offer(root);
        while (!dq.isEmpty()) {
            int size = dq.size();
            for (int i=0; i<size; ++i) {
                TreeNode node = dq.poll();
                temp.add(node.val);
                if (node.left != null)
                    dq.offer(node.left);
                if (node.right != null)
                    dq.offer(node.right);
            }
            result.add(new ArrayList<>(temp));
            temp.clear();
        }
        return result;
    }
}
